package map;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Created by fengliejv on 2020/4/19.
 */
public class LRUCache146 {
    class Node {
        Node pre;
        Node next;
        int value;
        int key;
        public Node(int key,int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {

        }
    }

    Map<Integer, Node> cache = new HashMap<>();
    Node head;
    Node last;
    int size;
    public LRUCache146(int capacity) {
        head = new Node();
        last = new Node();
        head.next = last;
        last.pre = head;
        this.size =capacity;
    }

    public int get(int key) {
        Node n = cache.get(key);
        if(n==null){
            return -1;
        }
        removeNode(n);
        addNodeTohead(n);
        return n.value;

    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            removeNode(node);
        }
        Node n = new Node(key,value);
        addNodeTohead(n);
        cache.put(key,n);
        if(cache.size()>size){
            removeLast();
        }

    }

    private void removeLast() {
        Node n = last.pre;
        if(n!=null){
            Node pre = n.pre;
            pre.next=last;
            last.pre = pre;
            cache.remove(n.key);
        }
    }

    private void addNodeTohead(Node n) {
        Node next = head.next;
        head.next = n;
        n.pre = head;
        n.next = next;
        next.pre = n;
    }

    private void removeNode(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
    }

}
